package week10

import "sort"

// 699. 掉落的方块
// https://leetcode-cn.com/problems/falling-squares/

func fallingSquares(positions [][]int) []int {
	// 离散化
	var mapp = make(map[int]int)
	var array []int
	for _, position := range positions {
		var left, right = position[0], position[0]+position[1]-1
		if _, ok := mapp[left]; !ok {
			mapp[left] = 0
			array = append(array, left)
		}
		if _, ok := mapp[right]; !ok {
			mapp[right] = 0
			array = append(array, right)
		}
	}
	sort.Sort(sort.IntSlice(array))
	for i, num := range array {
		mapp[num] = i
	}
	var ans []int
	var maxx = 0
	tree := BuildTree(array)
	for _, position := range positions {
		// 左右边界，高度
		var left, right, height = mapp[position[0]], mapp[position[0]+position[1]-1], position[1]
		var lastHeight = tree.Query(left, right) // 当前方块掉落前高度
		maxx = max(maxx, lastHeight+height)
		ans = append(ans, maxx)
		tree.Change(left, right, lastHeight+height) // 方块不能切割，整段区间直接覆盖为最新值
	}
	return ans
}

type Node struct {
	l, r int
	max int
	mark int
}

type StagementTree struct {
	list []Node
}

func BuildTree(array []int) *StagementTree {
	tree := &StagementTree{}
	tree.list = make([]Node, 4*len(array))
	tree.build(1, 0, len(array)-1, 0)
	return tree
}

func (tree *StagementTree) Build(left, right, height int) {
	tree.build(1, left, right, height)
}

func (tree *StagementTree) Query(left, right int) int {
	return tree.query(1, left, right)
}

func (tree *StagementTree) Change(left, right, val int) {
	tree.change(1, left, right, val)
}

func (tree *StagementTree) build(curr, l, r, val int) {
	tree.list[curr].l = l
	tree.list[curr].r = r
	if l == r {
		tree.list[curr].max = val
		return
	}
	var mid = (l + r) / 2
	tree.build(curr*2, l, mid, val)
	tree.build(curr*2+1, mid+1, r, val)
	tree.list[curr].max = max(tree.list[curr*2].max, tree.list[curr*2+1].max)
}

func (tree *StagementTree) query(curr, l, r int) int {
	if tree.list[curr].l >= l && tree.list[curr].r <= r {
		return tree.list[curr].max
	}
	tree.changeMark(curr)
	var ans = 0
	var mid = (tree.list[curr].l + tree.list[curr].r) / 2
	if l <= mid {
		ans = max(ans, tree.query(curr*2, l, r))
	}
	if r > mid {
		ans = max(ans, tree.query(curr*2+1, l, r))
	}
	return ans
}

func (tree *StagementTree) change(curr, l, r, val int) {
	if tree.list[curr].l >= l && tree.list[curr].r <= r {
		tree.list[curr].max = val
		tree.list[curr].mark = val
		return
	}
	tree.changeMark(curr)
	var mid = (tree.list[curr].l + tree.list[curr].r) / 2
	if l <= mid {
		tree.change(curr*2, l, r, val)
	}
	if r > mid {
		tree.change(curr*2+1, l, r, val)
	}
	tree.list[curr].max = max(tree.list[curr*2].max, tree.list[curr*2+1].max)
}

func (tree *StagementTree) changeMark(curr int) {
	// 直接覆盖为最新值
	val := tree.list[curr].mark
	if val != 0 {
		tree.list[curr*2].max = val
		tree.list[curr*2+1].max = val
		tree.list[curr*2].mark = val
		tree.list[curr*2+1].mark = val
		tree.list[curr].mark = 0
	}
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
